from sys import stdout
from time import time
from random import Random
from khronos.opt.base import Solver, RUNNING
from khronos.utils import Namespace, Deque, TrailableDict, INF
from khronos.statistics import Tally

# -----------------------------------------------
# Some constants used to configure the tree search
ORDER       = Namespace(DEPTH_FIRST="depth-first order",
                        BREADTH_FIRST="breadth-first order",
                        BEST_FIRST="best-first order (static ranking)",
                        DYNAMIC_BEST_FIRST="best-first order (dynamic ranking)",
                        RANDOM="random order",
                        CUSTOM="custom order")
DISCARDING  = Namespace(FRONT="discard from first position",
                        BACK="discard from last position",
                        RANDOM="discard from random position",
                        CUSTOM="custom discarding")
EXPLORATION = Namespace(EXPANSION="node expansion",
                        DIVING="node diving",
                        CUSTOM="custom exploration")
STATE       = Namespace(UNINITIALIZED=0,
                        INITIALIZED=1,
                        ONGOING=2)
# -----------------------------------------------

class TreeSearch(Solver):
    """This class implements a general and fully configurable tree search algorithm. The class 
    can be used without modifications for DFS, BFS, or best-first search. The class can also be 
    extended with custom search procedures by defining push(), pop(), discard() and explore().
    When using best-first order, two different node ranking schemes can be used:
        - STATIC ranking means nodes are ranked only once before going into the queue. The queue 
        is kept in order at all times. Node ranks can be updated at any time by calling the 
        rerank_queue() method, which causes a re-ranking and re-ordering of the entire queue. 
        Using rerank_queue(), a midterm between fully static and dynamic ranking is achieved.
        - in DYNAMIC ranking, the queue is not ordered; instead of ranking the nodes at insertion, 
        all queued nodes are ranked before fetching the next node to explore (highest rank node is 
        chosen). The fetch operation is thus computationally expensive in dynamic ranking.
        
    Please note that the solver is implemented for MINIMIZATION problems; to tackle maximization 
    problems, the symmetric of the problem's original objective function should be used (see the 
    documentation for TreeNode.objective()). For best-first and breadth-first schemes, in order to 
    obtain complete solutions quickly, diving can be used. The descent behavior of the algorithm 
    during a dive is fully configurable by redefining the descent() method, or calling dive() with
    different descent functions.
    Memory-bounding behavior can be optionally turned on, through the 'queue_size' configuration 
    parameter (default=INF). When the queue reaches the specified maximum size, after inserting 
    new nodes, the discard() method is called to turn the queue size back to the maximum. Finer 
    control of discarding can be achieved by redefining the discard() method and setting the 
    discarding rule to CUSTOM. If some bounding function is available, pruning can be enabled 
    through the 'pruning' flag, turning the algorithm into a branch-and-bound."""
    # Constants
    ORDER       = ORDER
    EXPLORATION = EXPLORATION
    DISCARDING  = DISCARDING
    STATE       = STATE
    INDLINE_FMT = "%40s: %s"
    # Default log and search configuration parameters
    default_log = True
    default = dict(order=ORDER.DEPTH_FIRST,           # search order
                   discarding=DISCARDING.RANDOM,      # discarding rule
                   exploration=EXPLORATION.EXPANSION, # exploration method
                   queue_size=INF,                    # maximum queue size
                   pruning=False)                     # pruning flag
    
    @classmethod
    def _default_config(cls):
        """This method builds a dictionary with the default parameters from each class in the 
        class hierarchy tree. This way, new configuration parameters may be added in subclasses 
        without disturbing the defaults set by superclasses."""
        config = dict()
        for klass in reversed(cls.mro()):
            try:
                config.update(klass.__dict__["default"])
            except KeyError:
                pass
        return config
        
    def __init__(self, **kwargs):
        Solver.__init__(self)
        self.rng = Random()           # pseudo-random number generator
        self.metadata = Namespace()   # search metadata
        self.init_params = dict()     # a dictionary with additional parameters passed to init()
        self.search = TrailableDict() # search control methods and attributes
        self.queue = None             # data structure for keeping yet unexplored nodes
        self.lower_bound = -INF       # lower bound on optimal objective value
        self.info = Namespace(state=STATE.UNINITIALIZED,      # current solver state
                              stop=[],                        # stoppage conditions
                              branching_factor=Tally(storing=False), # number of children per node
                              count=Namespace(iterations=0,   # main-loop iterations
                                              expansions=0,   # expansions completed
                                              dives=0,        # dives completed
                                              queued=0,       # queued nodes
                                              leaves=0,       # leaves reached
                                              pruned=0,       # pruned nodes
                                              discarded=0))   # discarded nodes
        self.max = Namespace(cpu=INF,          # cpu limit (seconds)
                             iterations=INF,   # mainloop iteration limit
                             improvements=INF) # improvement count limit
        self.root_fnc = None            # root function defining the start of the search
        config = self._default_config() # get default search configuration parameters
        config.update(kwargs)           # overwrite defaults with specified arguments
        self.set_search(**config)       # apply the resulting configuration
        
    def init(self, instance=None, cpu=INF, iterations=INF, improvements=INF, 
             root=None, upper_bound=INF, lower_bound=-INF, seed=None, **kwargs):
        """Solver initialization routine. This method initializes all solver attributes before 
        starting a new search, e.g. clear the queue, cpu clock, etc."""
        Solver.init(self, instance)
        if root is not None:
            self.root_fnc = root
        if seed is None:
            seed = int(time() * 1000)
        self.rng.seed(seed)
        self.metadata = Namespace(instance=self.instance, seed=seed)
        self.init_params = kwargs
        self.set_base_search()
        self.queue = self._new_queue()
        self.lower_bound = lower_bound
        # +++
        self.info.state = STATE.INITIALIZED
        self.info.stop = []
        self.info.count = Namespace((x, 0) for x in self.info.count.iterkeys())
        # +++
        self.max.cpu = cpu
        self.max.iterations = iterations
        self.max.improvements = improvements
        
    def _new_queue(self):
        """This method is called during the solver's initialization (init() method) to allow for 
        the creation of different types of queue structures. The default behavior of this method 
        is to return a khronos.utils.Deque object, but users may redefine this method and use 
        different data structures for holding open nodes.
        Regardless of the data structure's type, the queue object must always support a number of 
        methods which are used by the solver during the search:
            __len__()      length operator
            __iter__()     iteration operator
            __getitem__()  subscripting access   'var = queue[idx]' 
            __delitem__()  subscripting deletion 'del queue[idx]' 
            sort()         sorting method
        Additionally, the queue object may be used with the provided standard search functions 
        (DFS, BFS, Best-first, Random) if the following methods are supported:
            append()
            insort()
            pop()
            popleft()
        If these methods are not defined, then the user may have to use custom search functions 
        to have total control over how push, pop, and discard operations are done."""
        return Deque()
        
    def run(self, cpu=None, iterations=None, improvements=None):
        """The body of the search. If the search has not been bootstrapped yet, the _bootstrap() 
        method is called. Then, the main loop consists of getting a node from the queue (using 
        the search's pop method), and calling the exploration method on the returned node. The 
        loop terminates when one or more stoppage conditions are satisfied, e.g. the queue got 
        empty, or the CPU limit was reached."""
        # Early exit if the search is already finished.
        if self.info.state is STATE.UNINITIALIZED:
            self.log.error("initialize the solver before starting a new search")
            return None
        # Update all stoppage conditions.
        if any(limit is not None for limit in [cpu, iterations, improvements]):
            self.max.cpu = INF
            self.max.iterations = INF
            self.max.improvements = INF
            if cpu is not None:
                self.max.cpu = self.cpu.total + cpu
            if iterations is not None:
                self.max.iterations = self.info.count.iterations + iterations
            if improvements is not None:
                self.max.improvements = len(self.solutions) + improvements
        # Clear previous stoppage conditions.
        self.info.stop = []
        # Bootstrap if necessary.
        if self.info.state is STATE.INITIALIZED:
            with self.cpu.tracking():
                self._bootstrap()
        # The search's main loop.
        with self.cpu.tracking():
            try:
                while not self._stopped():
                    node = self.search["pop"]()
                    #self.log("pop() -> %s (%08x)" % (node.meta.id, id(node)))
                    self.search["explore"](node)
                    self.info.count.iterations += 1
            except KeyboardInterrupt:
                self.info.stop.append("keyboard interrupt")
        # Print stoppage conditions and return best solution found.
        for stoppage_condition in self.info.stop:
            self.log.warn(stoppage_condition)
        return self.solutions.best()
        
    def _bootstrap(self):
        """Bootstrap the search by generating and queueing the root node."""
        if self.info.state is not STATE.INITIALIZED:
            raise ValueError("please initialize the solver before bootstrapping")
        if self.root_fnc is None:
            self.root_fnc = self.__class__.Node.root
        root = self.root_fnc(self)
        self._dispatch_node(root)
        if self.search["pruning"]:
            self.lower_bound = max(self.lower_bound, root.meta.lower_bound)
        self.info.state = STATE.ONGOING
        self.state = RUNNING
        
    def _stopped(self):
        """This method returns True if some stoppage condition has been satisfied."""
        if len(self.queue) == 0:
            self.info.stop.append("empty queue")
        if self.cpu.total >= self.max.cpu:
            self.info.stop.append("cpu limit reached")
        if self.info.count.iterations >= self.max.iterations:
            self.info.stop.append("iteration limit reached")
        return len(self.info.stop) > 0
        
    def _expand(self, node, branches=None):
        """Expand a list of branches applied to a given node to create a list of child nodes. 
        This method behaves differently depending on the return value of the branches() method 
        of the argument node. If branches() returns a list of TreeNode objects, then _expand() 
        assumes these are already children of the argument node, and simply establishes the 
        connection between the metadata of both nodes (to correctly assign ids and count the 
        number of children at the parent node). If branches() returns something other than 
        TreeNode objects, _explore() assumes this is data to apply a modification to the given 
        node, thus a copy is made and the modification is applied to create a child node for 
        each element of this list. In any case, these child nodes are then placed in the queue 
        if possible, to be explored later."""
        if branches is None:
            branches = node.branches()
            self.info.branching_factor.collect(len(branches))
        for branch in branches:
            if isinstance(branch, TreeNode):
                child = branch
                node.meta.link_child(child.meta)
            else:
                child = node.copy()
                node.meta.link_child(child.meta)
                child.apply(branch)
            self._dispatch_node(child)
        self.info.count.expansions += 1
        
    def _dive(self, node, descent_fnc=None, abort=INF):
        """Make a dive starting at the given node. The path of the dive and expansion of nodes 
        during the descent can be controlled by the 'descent_fnc()' argument. For more information 
        about 'descent_fnc()', please refer to the documentation of the descent() method.
        If pruning is enabled, the dive is aborted whenever the node's LB becomes greater or 
        equal to the current UB multiplied by the specified 'abort' value. Note that this behavior 
        can be prevented by using large enough values for the 'abort' argument (default=INF).
        The _dive() method returns the final node, whether it is a leaf if the dive completed 
        successfully, or an intermediate node if the dive aborted. The completion state of the 
        dive can be easily checked by inspecting the 'leaf' attribute of the returned node.
            TODO: extend the dive function to support selecting the dive path and expansion nodes 
        only AFTER creating the child nodes (e.g. to select the child node with best lower bound 
        as dive path, and/or only child nodes with the X best lower bounds to be queued."""
        if descent_fnc is None:
            descent_fnc = self.descent
        abort_value = abort * self.upper_bound
        dive_node = node.copy()
        node.meta.link_dive(dive_node.meta)
        while True:
            dive_path, to_expand = descent_fnc(dive_node)
            if len(to_expand) > 0:
                self._expand(dive_node, to_expand)
            if isinstance(dive_path, TreeNode):
                dive_node.link_dive(dive_path.meta)
                dive_node = dive_path
            else:
                dive_node.apply(dive_path)
            if dive_node.is_leaf():
                self._check_solution(dive_node)
                break
            if self.search["pruning"] and dive_node.lower_bound() >= abort_value:
                break
        self.info.count.dives += 1
        return dive_node
        
    def descent(self, node):
        """OPTIONAL METHOD FOR DIVING
            descent() :: TreeNode -> (dive_path, [dive_expand_branches])
        This method is used in dives to guide the direction of descent as well as the expansion
        of branches into the queue during the dive. This method should return a tuple containing 
        the dive path and a list of branches to be expanded (can be an empty list).
        The default behavior is to obtain the list of all branches at the given node (using the 
        branches() method), removing the last branch the from list, and using it as the dive 
        path. The remaining branches are returned as expansion branches. The behavior of dives 
        can be customized by redefining this method."""
        dive_branches = node.branches()
        dive_path = dive_branches.pop()
        return dive_path, dive_branches
        
    def _dispatch_node(self, node):
        """This method checks and sends nodes to their correct destinations. If the argument node 
        is a leaf, it is checked for improvement. Otherwise, if pruning is enabled, the node's 
        lower bound is checked. Finally, if the node is not pruned, it is added to the queue.
        If, after queuing the node, the queue is exceeding its maximum size, the discard() 
        method is used to reduce the queue to the maximum size allowed."""
        if node.meta.leaf:
            self._check_solution(node)
            return
        if self.search["pruning"] and node.meta.lower_bound >= self.upper_bound:
            self.info.count.pruned += 1
            return
        self.search["push"](node)
        self.info.count.queued += 1
        if len(self.queue) > self.search["queue_size"]:
            self.search["discard"]()
            self.info.count.discarded += 1
            
    # -----------------------------------------------------
    # Methods for complete solutions (leaf nodes) ---------
    def _check_solution(self, leaf):
        """Check a leaf node's objective function value. If it is less that the current upper 
        bound, we record the solution into the solution list, tighten the upper bound, and, if 
        pruning is enabled, prune the queue with the new bound. The search is stopped at this 
        point if an optimal solution is found or the desired number of improvements has been 
        reached."""
        if leaf.meta.objective < self.upper_bound:
            metadata = dict(self.metadata)
            metadata.update(self.info.count)
            metadata.update(queue_occupation=len(self.queue), 
                            branching_factor=self.info.branching_factor.mean(),
                            search_speed=(self.info.count.iterations + 1) / self.cpu.total)
            metadata.update(leaf.leaf_metadata())
            self._log_solution(self.add_solution(leaf, leaf.meta.objective, **metadata))
            if len(self.solutions) >= self.max.improvements:
                self.info.stop.append("improvement limit reached")
            if leaf.meta.objective <= self.lower_bound:
                self.info.stop.append("optimal solution found")
            elif self.search["pruning"] and len(self.queue) > 0:
                self._prune_queue()
        self.info.count.leaves += 1
        
    def _log_solution(self, solution):
        """Print a description of a given solution using the logger object."""
        self.log("=" * 100)
        for key, value in sorted(solution.metadata.iteritems()):
            self.log(self.INDLINE_FMT % (key, value), width=100)
        self.log("=" * 100)
        
    # -----------------------------------------------------
    # Queue-related methods -------------------------------
    def _prune_queue(self):
        """Queue pruning, called after an update to the upper bound. Nodes are removed from the 
        queue if their lower bound is greater or equal to the new upper bound, i.e. they cannot 
        possibly lead to solutions better than the new upper bound."""
        total = len(self.queue)
        pruned = 0
        kept = 0
        while kept + pruned < total:
            if self.queue[kept].meta.lower_bound >= self.upper_bound:
                del self.queue[kept]
                pruned += 1
            else:
                kept += 1
        self.log("QUEUE PRUNING: Total %d, Kept %d, Pruned %d" % (total, kept, pruned))
        self.info.count.pruned += pruned
        
    def _rerank_queue(self):
        """Causes a recomputation of the ranks of all queued nodes, and a reordering of the queue. 
        This method should be called manually in static-ranking best-first search, to help 
        implement adaptive ranking mechanisms, e.g. periodically reorder the queue according to 
        a ranking function which learns and adapts from the search done so far."""
        for node in self.queue:
            node.meta._rank = node.rank()
        self.queue.sort()
        
    def _verify_queue(self, check_ranks=True):
        """Perform a sanity check to the contents of the queue. If any node is out of order 
        rank-wise or a node's LB is greater or equal to the current UB (if pruning is enabled), 
        an error message is printed. This method returns the number of errors that were caught."""
        errors = 0
        if len(self.queue) > 0:
            if check_ranks:
                self.log("Checking rank order...")
                prev_rank = self.queue[0].meta.rank
                for index, node in enumerate(self.queue):
                    if node.meta.rank < prev_rank:
                        self.log.error("Rank inversion at position %d (%s > %s)" % 
                                       (index, prev_rank, node.meta.rank))
                        errors += 1
                    prev_rank = node.meta.rank
            if self.search["pruning"]:
                self.log("Checking lower-bounds...")
                for index, node in enumerate(self.queue):
                    if node.meta.lower_bound >= self.upper_bound:
                        self.log.error("Non-improving node at position %d" % (index,))
                        errors += 1
        self.log.warn("%d errors found" % (errors,))
        return errors
        
    # -----------------------------------------------------
    # Methods related to search strategy ------------------
    def set_base_search(self):
        """Reverts the search TrailableDict to its base values, i.e. pops everything until the 
        dictionary's main stack has only one entry (which contains the base values of all search 
        parameters)."""
        while len(self.search._main_stack) > 1:
            self.search.pop()
            
    def set_search(self, order=None, discarding=None, exploration=None, 
                   queue_size=None, pruning=None, **kwargs):
        """Configure the algorithm's behavior, including the search order scheme, discarding 
        rules, exploration method, maximum queue size, pruning, and any configuration parameters 
        that may be necessary in subclasses. The values are set (not pushed) in the 'search' 
        trailable dictionary."""
        if order is not None: 
            fnc_map = {ORDER.DEPTH_FIRST:        (self._append, self._pop),
                       ORDER.BREADTH_FIRST:      (self._append, self._pop_left),
                       ORDER.BEST_FIRST:         (self._insort, self._pop),
                       ORDER.DYNAMIC_BEST_FIRST: (self._append, self._pop_best),
                       ORDER.RANDOM:             (self._append, self._pop_random),
                       ORDER.CUSTOM:             (self.push, self.pop)}
            push_fnc, pop_fnc = fnc_map.get(order, order)
            self.search.set(push=push_fnc, pop=pop_fnc, order=order)
        if discarding is not None: 
            fnc_map = {DISCARDING.FRONT:  self._pop_left,
                       DISCARDING.BACK:   self._pop,
                       DISCARDING.RANDOM: self._pop_random,
                       DISCARDING.CUSTOM: self.discard}
            self.search.set(discard=fnc_map.get(discarding, discarding), 
                            discarding=discarding)
        if exploration is not None:
            fnc_map = {EXPLORATION.EXPANSION: self._expand,
                       EXPLORATION.DIVING:    self._dive,
                       EXPLORATION.CUSTOM:    self.explore}
            self.search.set(explore=fnc_map.get(exploration, exploration), 
                            exploration=exploration)
        if queue_size is not None:
            self.search.set(queue_size=queue_size)
        if pruning is not None:
            self.search.set(pruning=pruning)
        self.search.set(**kwargs)
        
    def push_search(self, *args, **kwargs):
        """The same as set_search(), but the values are pushed (instead of simply set) into the 
        'search' trailable dictionary, thus allowing the user to go back to the previous values 
        by calling the pop() method on this dictionary."""
        self.search.push() # create a new entry in the TrailableDict's main stack
        self.set_search(*args, **kwargs)
        
    def _append(self, node):
        self.queue.append(node)
        
    def _insort(self, node):
        self.queue.insort(node)
        
    def _pop(self):
        return self.queue.pop()
        
    def _pop_left(self):
        return self.queue.popleft()
        
    def _pop_best(self):
        best_idx = None
        best_rank = None
        for idx, node in enumerate(self.queue):
            node_rank = node.rank()
            if node_rank > best_rank:
                best_rank = node_rank
                best_idx = idx
        best_node = self.queue[best_idx]
        del self.queue[best_idx]
        return best_node
        
    def _pop_random(self):
        idx = self.rng.randint(0, len(self.queue) - 1)
        node = self.queue[idx]
        del self.queue[idx]
        return node
        
    def push(self, node):
        """REQUIRED FOR CUSTOM SEARCH ORDER
            push() :: TreeNode -> 
        Define how a node is added (pushed) to the queue.
        NOTE: The solver's queue of open nodes can be accessed through the 'queue' attribute."""
        raise NotImplementedError()
        
    def pop(self):
        """REQUIRED FOR CUSTOM SEARCH ORDER
            pop() :: -> TreeNode
        Define how nodes should be fetched from the queue prior to exploration.
        NOTE: The solver's queue of open nodes can be accessed through the 'queue' attribute."""
        raise NotImplementedError()
        
    def discard(self):
        """REQUIRED FOR CUSTOM DISCARDING RULE
            discard() :: -> 
        Discard a node from the queue. This method is used if the CUSTOM discarding rule is 
        selected. The discard() method is called when the maximum queue size was exceeded after 
        an insertion.
        NOTE: The solver's queue of open nodes can be accessed through the 'queue' attribute."""
        raise NotImplementedError()
        
    def explore(self, node):
        """REQUIRED FOR CUSTOM EXPLORATION METHOD
            explore() :: TreeNode -> 
        Define how a node should be explored. The default options are simple expansion or 
        diving, but new ways may be created by setting the 'exploration' configuration parameter 
        to CUSTOM and redefining this method."""
        raise NotImplementedError()
        
    # -----------------------------------------------------
    # Utilities -------------------------------------------
    def show_nodes(self, start=0, n=INF):
        """Starting from index 'start', print 'n' nodes from the queue."""
        for x in xrange(start, min(start + n, len(self.queue))):
            print "\t", x, "::", self.queue[x]
            
    def first_nodes(self, n=10):
        """Print the first n nodes on the queue."""
        n = min(n, len(self.queue))
        print "Showing first %d nodes" % (n,)
        self.show_nodes(0, n)
        
    def last_nodes(self, n=10):
        """Print the last n nodes on the queue."""
        n = min(n, len(self.queue))
        print "Showing last %d nodes" % (n,)
        self.show_nodes(len(self.queue) - n, n)
        
    def edge_nodes(self, n=10):
        """Print the first and last n nodes on the queue."""
        if len(self.queue) <= 2*n:
            print "Showing all nodes"
            self.show_nodes()
        else:
            self.first_nodes(n)
            self.last_nodes(n)
            
    def report(self, show_solutions=True, out=stdout):
        """Write a summary of the solver's configuration, current search state and a summary of 
        the solutions found so far."""
        fmt = self.INDLINE_FMT + "\n"
        out.write(object.__repr__(self) + "\n")
        for key, value in sorted(self.search.iteritems()):
            if callable(value):
                value = value.__name__
            out.write(fmt % (key, value))
        if self.instance is not None:
            occup = len(self.queue)
            occup_percent = 100.0 * occup / self.search["queue_size"]
            search_speed = self.info.count.iterations / self.cpu.total if self.cpu.total else 0.0
            for key, value in [("Queue occupation", "%d (%.3f %%)" % (occup, occup_percent)),
                               ("Search speed",     "%.3f iter/sec" % (search_speed,)),
                               ("Total CPU time",   self.cpu.total),
                               ("Branching factor", self.info.branching_factor.mean()),
                               ("Iterations",       self.info.count.iterations),
                               ("Expansions",       self.info.count.expansions),
                               ("Dives",            self.info.count.dives),
                               ("Queued nodes",     self.info.count.queued),
                               ("Pruned nodes",     self.info.count.pruned),
                               ("Discarded nodes",  self.info.count.discarded),
                               ("Leaves reached",   self.info.count.leaves),
                               ("Upper bound",      self.upper_bound),
                               ("Solutions found", len(self.solutions))]:
                out.write(fmt % (key, value))
            if show_solutions:
                for x, sol in enumerate(self.solutions):
                    obj = sol.metadata.objective
                    cpu = sol.metadata.cpu
                    out.write(fmt % (x, "z = %s (obtained at %s)" % (obj, cpu)))
                    
class TreeNode(object):
    """
    Subclasses should define the methods listed below: methods marked with * are recommended, and 
    methods marked with ** are optional. Please refer to the documentation on these methods for 
    more information on their role in the algorithm, and what they should implement.
        root()          # create the starting point of the search
        copy()          # create an exact (deep) copy of a node
        branches()      # list of branching options available at a node
        apply(branch)   # modify a node by following a given branch
        objective()     # compute the objective function value of a node
        *is_leaf()      # check whether a node is a leaf or not
        **lower_bound() # compute a lower bound of the objective function for a node
        **rank()        # compute the rank of a node (for best-first only)
    """
    def __init__(self):
        self.meta = TreeNodeMeta(self)
        
    def __cmp__(self, node):
        return cmp(self.meta.rank, node.meta.rank)
        
    @classmethod
    def root(cls, solver):
        """MANDATORY METHOD
            root() :: solver -> TreeNode
        Given a reference to the solver, create and return the starting point of the search."""
        raise NotImplementedError()
        
    def copy(self):
        """MANDATORY METHOD
            copy() :: -> TreeNode
        Create an exact copy of the given node (except it's metadata!). This method is extensively 
        used because a lot of node copies are necessary while expanding a node's children. Extreme 
        care should be taken for shared information between nodes. If the shared data can somehow 
        be modified then each node should contain an independent copy of that data."""
        raise NotImplementedError()
        
    def branches(self):
        """MANDATORY METHOD
            branches() :: -> [branch]
        Create a list of branches available at a given node. The elements of the branch list 
        should contain all the necessary information to apply a change to a node. Instead of 
        returning a list of data to apply modifications to a node, this method may directly 
        create and return a list of TreeNode objects. In that case, the apply() method does not 
        have to be redefined, since it will not be used."""
        raise NotImplementedError()
        
    def apply(self, branch):
        """MANDATORY METHOD (if branches() does not create nodes)
            apply() :: branch ->
        Apply a modification, corresponding to following the given branch in the tree (an element 
        of the branch list returned by the branches() method) to a node IN-PLACE!"""
        raise NotImplementedError()
        
    def objective(self):
        """MANDATORY METHOD
            objective() :: -> z-value
        Calculate and return the objective function value of a given leaf node. Care must be taken 
        in the definition of this function, since the solver is programmed to tackle minimization 
        problems. For maximization problems, simply use the symmetric of the original objective 
        function, i.e. max f(X) becomes min -f(X)."""
        raise NotImplementedError()
        
    def is_leaf(self):
        """REDEFINITION RECOMMENDED
            is_leaf() :: -> bool
        Return a boolean indicating whether the given node is a leaf or not. It is advisable to 
        redefine this method in subclasses, but it's default behavior should work without problem, 
        although much slower than with an application-specific 'leafness' check. By default, a 
        node is considered a leaf if its list of available branches is empty."""
        return len(self.branches()) == 0
        
    def lower_bound(self):
        """REQUIRED FOR PRUNING
            lower_bound() :: -> LB
        Calculate and return a lower bound of the best objective function value (z) that can be 
        obtained through a given node. Note that returning a value which is not a real lower bound 
        may cause incorrect pruning decisions."""
        raise NotImplementedError()
        
    def rank(self):
        """REQUIRED FOR BEST-FIRST SEARCH
            rank() :: -> node_rank
        Calculate and return the rank of a node. The rank is used to define the order by which 
        nodes are explored in best-first search."""
        raise NotImplementedError()
        
    def leaf_metadata(self):
        """This method is called on leaf nodes when the upper bound was improved and the solution 
        in this node is being added to the solution list. The method should return a dictionary of 
        metadata to be added to the final solution's metadata dictionary."""
        return ()
        
class TreeNodeMeta(object):
    """Data structure used for holding tree nodes' metadata.
    Attributes (names marked with * are lazy attributes):
        id - node identifier
        child_count - child nodes counter
        dive_count - dive nodes counter
        depth - level of the node on the tree
        *leaf - boolean indicating whether the node is a leaf or not
        *objective - objective function value of the node (only for leaf nodes)
        *lower_bound - lower bound of the objective function value obtained through this node
        *rank - the node's rank (for positioning in the queue in best-first search)
    """
    def __init__(self, node):
        self.node = node
        self.id = TreeNodeID.ROOT_ID
        self.child_count = 0
        self.dive_count = 0
        self._leaf = None
        self._objective = None
        self._lower_bound = None
        self._rank = None
        
    def __repr__(self):
        return str(self.id)
        
    def link_child(self, child_meta):
        if not self.id.is_parent_of(child_meta.id):
            child_meta.id = TreeNodeID(self.id, str(self.child_count))
            self.child_count += 1
            
    def link_dive(self, dive_meta):
        if not self.id.is_parent_of(child_meta.id):
            dive_meta.id = TreeNodeID(self.id, "D%d" % (self.dive_count,))
            self.dive_count += 1
            
    @property
    def depth(self):
        return len(self.id)
        
    @property
    def leaf(self):
        if self._leaf is None:
            self._leaf = self.node.is_leaf()
        return self._leaf
        
    @leaf.deleter
    def leaf(self):
        self._leaf = None
        
    @property
    def objective(self):
        if not self.leaf:
            raise TypeError("objective function value is only available for leaf nodes")
        if self._objective is None:
            self._objective = self.node.objective()
        return self._objective
        
    @objective.deleter
    def objective(self):
        self._objective = None
        
    @property
    def lower_bound(self):
        if self._lower_bound is None:
            self._lower_bound = self.node.lower_bound()
        return self._lower_bound
        
    @lower_bound.deleter
    def lower_bound(self):
        self._lower_bound = None
        
    @property
    def rank(self):
        if self._rank is None:
            self._rank = self.node.rank()
        return self._rank
        
    @rank.deleter
    def rank(self):
        self._rank = None
        
class TreeNodeID(object):
    """A special-purpose class for node identifiers. An id is simply a pair (parent_id, child_no),
    where parent_id is another TreeNodeID object. The depth of a node can be checked by calling 
    the __len__() method."""
    def __init__(self, parent_id, child_no):
        self.parent_id = parent_id
        self.child_no = child_no
        self.__str = None
        self.__len = None
        
    def __str__(self):
        if self.__str is None:
            self.__str = self.str()
        return self.__str
        
    def __len__(self):
        if self.__len is None:
            self.__len = self.depth()
        return self.__len
        
    def is_child_of(self, node_id):
        return self.parent_id is node_id
        
    def is_parent_of(self, node_id):
        return node_id.parent_id is self
        
    def str(self):
        parts = []
        target = self
        while target.parent_id is not None:
            parts.append(target.child_no)
            target = target.parent_id
        parts.append(target.child_no)
        parts.reverse()
        return ".".join(parts)
        
    def depth(self):
        depth = 0
        target = self
        while target.parent_id is not None:
            depth += 1
            target = target.parent_id
        return depth
        
TreeSearch.Node = TreeNode
TreeNodeID.ROOT_ID = TreeNodeID(None, "R")
